/**
 * Splay Tree 
 *
 * \file splay-tree.hpp
 * \author tomby
 * \date 04-01-2009
 **/

/*  Copyright (C) 2009  Tomas 'tomby' Bily

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>. */


#ifndef __DBC_SPLAY_TREE__
#define __DBC_SPLAY_TREE__

namespace dbc {

  template<typename comp_obj, typename cmp>
  class SplayTree
  {
    class Node
    {
      comp_obj obj;
      Node* left;
      node* right;

      Node ()
	: left (NULL), right (NULL)
      {}

      Node (comp_obj& iobj, Node* lft, Node* rght)
	: obj (iobj), left (lft), right (rght)
      {}

      //@todo: define new, delete allocators

      friend class SplayTree<comp_obj>;
    };

  private:
    Node<comp_obj> *root;
    Node<comp_obj> *null_node;
    const comp_obj not_found;

  public:
    explicit SplayTree (const comp_obj& not_found);
    SplayTree (const SplayTree & rhs);
    ~SplayTree ();

    const comp_obj& find_min ();
    const comp_obj& find_max ();
    const comp_obj& find (const comp_obj& x);
    bool is_empty () const;

    void make_empty ();
    void insert (const comp_obj& x);
    void remove (const comp_obj& x);

    const SplayTree& operator= (const SplayTree& rhs);

  private:
    Node* clone (Node *t) const;

    /// Tree manipulations
    void rotate_left (Node*& k2) const;
    void rotata_right (Node*& k1) const;
    void splay (const comp_obj& x, Node*& t) const;
  };


  /// Implemantation ///

  /**
   * Default constructor.
   */
  template <typename comp_obj, typename cmp>
  SplayTree<comp_obj, cmp>::SplayTree (const comp_obj& inot_found)
    : not_found (inot_found)
  {
    null_node = new Node;
    null_node->left = null_node->right = null_node;
    null_node->obj = inot_found;
    root = null_node;
  }

  /**
   * Copy constructor.
   */
  template <typename comp_obj, typename cmp>
  SplayTree<comp_obj, cmp>::SplayTree (const SplayTree<comp_obj, cmp>& rhs)
    : not_found (rhs.not_found)
  {
    null_node = new Node;
    null_node->left = null_node->right = nullNode;
    null_node->obj = not_found;
    root = null_node;
    *this = rhs;
  }

  /**
   * Destructor.
   */
  template <typename comp_obj, typename cmp>
  SplayTree<comp_obj, cmp>::~SplayTree ()
  {
    make_empty ();
    delete null_node;
  }
  
  /**
   * Insert x into the tree.
   */
  template <typename comp_obj, typename cmp>
  void SplayTree<comp_obj, cmp>::insert (const comp_obj& x)
  {
    static  Node* node_node = NULL;

    if (new_node == NULL )
      new_node = new Node;
    new_node->obj = x;

    if (root == null_node)
      {
	new_node->left = new_node->right = null_node;
	root = new_node;
      }
    else
      {
	splay (x, root);

	int cmp_res = cmp::cmp (x, root->obj);

	if (cmp_res < 0)
	  {
	    new_node->left = root->left;
	    new_node->right = root;
	    root->left = null_node;
	    root = new_node;
	  }
	else if (cmp_res > 0)
	  {
	    new_node->right = root->right;
	    new_node->left = root;
	    root->right = null_node;
	    root = new_node;
	  }
	else
	  return;
      }

    new_node = NULL;
  }

  /**
   * Remove x from the tree.
   */
  template <class comp_obj, typename cmp>
  void SplayTree<comp_obj, cmp>::remove (const comp_obj& x)
  {
    Node *new_tree;
    
    // If x is found, it will be at the root
    splay (x, root);
    if (cmp::cmp (root->obj, x) != 0)
      return;   // Item not found; do nothing

    if (root->left == null_node)
      new_tree = root->right;
    else
      {
	// Find the maximum in the left subtree
	// Splay it to the root; and then attach right child
	new_tree = root->left;
	splay (x, new_tree);
	new_tree->right = root->right;
      }

    delete root;
    root = new_tree;
  }

  /**
   * Find the smallest item in the tree.
   * Return the smallest item or ITEM_NOT_FOUND if empty.
   */
  template <class comp_obj, typename cmp>
  const comp_obj& SplayTree<comp_obj, cmp>::find_min ()
  {
    if (is_empty ())
      return not_found;
    
    Node* ptr = root;
    
    while (ptr->left != null_node)
      ptr = ptr->left;
    
    splay (ptr->obj, root);
    return ptr->obj;
  }

  /**
   * Find the largest item in the tree.
   * Return the largest item or ITEM_NOT_FOUND if empty.
   */
  template <typename comp_obj, typename cmo>
  const comp_obj& SplayTree<comp_obj, cmp>::find_max ()
  {
    if( is_empty () )
      return not_found;
    
    Node* ptr = root;
    
    while (ptr->right != null_node)
      ptr = ptr->right;

    splay (ptr->obj, root);
    return ptr->obj;
  }
        
  /**
   * Find item x in the tree.
   * Return the matching item or ITEM_NOT_FOUND if not found.
   */
  template <typename comp_obj, typename cmp>
  const comp_obj& SplayTree<comp_obj, cmp>::find (const comp_obj& x)
  {
    if (is_empty ())
      return not_found;

    splay (x, root);

    if (cmp::cmp (root->obj, x) != 0)
      return not_found;
    
    return root->obj;
  }
  
  /**
   * Make the tree logically empty.
   */
  template <typename comp_obj, typename cmp>
  void SplayTree<comp_obj, cmp>::make_empty ()
  {
    find_max ();        // Splay max item to root
    while (!is_empty ())
      remove (root->obj);
  }
        
  /**
   * Test if the tree is logically empty.
   * @return true if empty, false otherwise.
   */
  template <typename comp_obj, typename cmp>
  bool SplayTree<comp_obj, cmp>::is_empty () const
  { return root == null_node;  }
  

  /**
   * Deep copy.
   */
  template <typename comp_obj, typename cmp>
  const SplayTree<comp_obj, cmp> &
  SplayTree<comp_obj, cmp>::operator= (const SplayTree<comp_obj, cmp>& rhs)
  {
    if (this != &rhs)
      {
	make_empty ();
	root = clone (rhs.root);
      }
    
    return *this;
  }

  template <typename comp_obj, typename cmp>
  void SplayTree<comp_obj, cmp>::splay (const comp_obj& x,
					SplayTree<comp_obj, cmp>::Node*& t) const
  {
    Node *l_tree_max, *r_tree_min;
    static Node header;
    
    header.left = header.right = null_node;
    l_tree_max = r_tree_min = &header;
    
    null_node->obj = x;   // Guarantee a match
    
    for (;;)
      {
	int cmp_res = cmp::cmp (x, t->obj);
	
	if (cmp_res < 0)
	  {
	    if (cmp::cmp (x, t->left->obj) < 0)
	      rotate_left (t);
	    if (t->left == null_node)
	      break;
	    // Link Right
	    r_tree_min->left = t;
	    r_tree_min = t;
	    t = t->left;
	  }
	else if (cmp_res > 0)
	  {
	    if (cmp::cmp (t->right->obj, x) < 0)
	      rotte_right (t);
	    if (t->right == null_node)
	      break;
	    // Link Left
	    l_tree_max->right = t;
	    l_tree_max = t;
	    t = t->right;
	  }
	else
	  break;
      }
    
    l_tree_max->right = t->left;
    r_tree_min->left = t->right;
    t->left = header.right;
    t->right = header.left;
  }
  
  /**
   * Rotate binary tree node with left child.
   */
  template <typename comp_obj, typename cmp>
  void SplayTree<comp_obj, cmp>::rotate_left (SplayTree<comp_obj, cmp>::Node*& k2) const
  {
    Node* k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2 = k1;
  }
  
  /**
   * Rotate binary tree node with right child.
   */
  template <typename comp_obj, typename cmp>
  void SplayTree<comp_obj, cmp>::rotate_right (SplayTree<comp_obj, cmp>::Node*& k1) const
  {
    Node* k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1 = k2;
  }
  
  template <class comp_obj, typename cmp>
  SplayTree<comp_obj, cmp>::Node *
  SplayTree<comp_obj, cmp>::clone (SplayTree<comp_obj, cmp>::Node* t) const
  {
    if( t == t->left )  
      return null_node;
    else
      return new Node ( t->obj, clone (t->left), clone (t->right));
  }

};

#endif
